from typing import List


# 123. 买卖股票的最佳时机 III
# 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
# 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
def maxProfit(prices: List[int]) -> int:
    # 状态转移方程
    # 每一天有五种状态
    # 1、没有进行交易
    # 2、进行了一次买交易
    # 3、进行了一次买交易，进行了一次卖交易
    # 4、进行了一次买交易，进行了一次卖交易。进行了第二次买交易
    # 5、进行了一次买交易，进行了一次卖交易。进行了第二次买交易，进行了第二次卖交易

    len_prices = len(prices)

    # 边界值，第一天买入卖出
    buy_1 = -prices[0]
    sell_1 = 0
    buy_2 = -prices[0]
    sell_2 = 0

    print("start".rjust(20, "="))
    print(f"buy_1:{buy_1},sell_1:{sell_1},buy_2:{buy_2},sell_2:{sell_2}")

    # 设置初始的值
    for day in range(1, len_prices):
        # 买入尽量取最小值
        buy_1 = max(buy_1, -prices[day])
        # 卖出尽量取最大值
        sell_1 = max(sell_1, buy_1 + prices[day])

        buy_2 = max(buy_2, sell_1 - prices[day])
        sell_2 = max(sell_2, buy_2 + prices[day])
        print(f"{day} day ----> {prices[day]}  buy_1:{buy_1},sell_1:{sell_1},buy_2:{buy_2},sell_2:{sell_2}")

    print(f"buy_1:{buy_1},sell_1:{sell_1},buy_2:{buy_2},sell_2:{sell_2}")
    print("end".rjust(20, "="))

    return sell_2


prices_1 = [3, 3, 5, 0, 0, 3, 1, 4]
result = maxProfit(prices_1)
print(f"result:{result}")

prices_1 = [1, 2, 3, 4, 5]
result = maxProfit(prices_1)
print(f"result:{result}")

prices_1 = [7, 6, 4, 3, 1]
result = maxProfit(prices_1)
print(f"result:{result}")

prices_1 = [1]
result = maxProfit(prices_1)
print(f"result:{result}")

prices_1 = [1, 7, 1, 7, 1, 7, 1, 7]
result = maxProfit(prices_1)
print(f"result:{result}")
